#include "stdio.h"
#include "stdlib.h"
#define LIST_INIT_SIZE 100 //初始容量 
#define LIST_INCREMENT 10 //追加内存时的增量 
typedef int ElemType; // 简单起见，每个元素定为int型 
typedef struct{ 
    ElemType *elem; //连续内存首地址 
    int length; //表长 
    int size; //表容量（最多能够存放的元素个数） 		
}SqList; //类型别名

/**
 * @brief 初始化
 * 
 * @param L 自定义顺序表 
 */
void init(SqList &L){
    //分配内存
    L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));
    
    if(!L.elem){//内存分配失败
        exit(-1);
    }

    L.length = 0;
    L.size = LIST_INIT_SIZE;
}

/**
 * @brief 得到顺序表对应位置的元素,存放在e
 * 
 * @param L 顺序表
 * @param i 下标（1开始）
 * @param e 存放在e
 */
void getElem(SqList L, int i, ElemType &e){
    if(i < 1 || i > L.length){
        return;
    }
    e = L.elem[i - 1];
}

/**
 * @brief 向顺序表插入一个元素
 * 
 * @param L 顺序表
 * @param i 位置（从1开始）
 * @param e 元素
 */
void insert(SqList &L, int i, ElemType e){
    if(i < 1 || i > L.length + 1){
        return;
    }

    if(L.length == L.size){//内存不足
        ElemType *base = (ElemType *)realloc(L.elem, (L.size + LIST_INCREMENT) * sizeof(ElemType));
        if(!base){//内存分配失败
            exit(-1);
        }
        //更换首地址
        L.elem = base;
        //更换容量
        L.size = L.size + LIST_INCREMENT;
    }
    //i位置及以后的需要向后移
    for(int j = L.length - 1; j >= i - 1; j--){
        L.elem[j + 1] = L.elem[j];
    }
    //插入
    L.elem[i - 1] = e;
    //长度加一
    L.length ++;
}

/**
 * @brief 从顺序表删除一个元素（顺序第一个出现的）
 * 
 * @param L 顺序表
 * @param i 位置（从1开始）
 * @param e 元素
 */
void del(SqList &L, int i, ElemType &e){
    if(i < 1 || i > L.length){
        return;
    }
    //存放删除的元素（如果需要）
    e = L.elem[i -1];
    for(int j = i - 1; j < L.length - 1; j++){
        L.elem[j] = L.elem[j+1];
    }

    L.length--;
}

/**
 * @brief 查找元素
 * 
 * @param L 顺序表
 * @param e 元素
 * @param i 存放查找到的元素下标
 */
void find(SqList L, ElemType e, int &i){
    i = 1;
    while(i <= L.length && L.elem[i - 1] != e){
        i++;
    }
    //没找到
    if(i > L.length){
        i = -1;
    }
}

/**
 * @brief print sequal list to console
 * 
 * @param list 
 */
void printSqList(SqList list){
    for (int i = 0; i < list.length; i++)
    {
        printf("%d\t", list.elem[i]);
    }
    printf("\n长度:%d\n", list.length);
    printf("大小:%d\n", list.size);
}